package Acwing.搜索与图论;

import java.util.Scanner;

/**
 * @Title: arrangeTheNumbers
 * @Author 贾金博
 * @Package Acwing.搜索与图论
 * @Date 2025/4/11 下午6:11
 * @description: 排列数字
 */
public class arrangeTheNumbers {

    private static int n;
    private static int[] a;
    private static boolean[] st; // 表明当前这个数有没有被用过

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n + 10];
        st = new boolean[n + 10];

        for(int i = 1; i <= n; i++) {
            a[i] = i;
        }

        // 开始进行排列
        dfs(1);
    }

    private static void dfs(int len) {
        if(len == n + 1) {
            for(int i = 1; i <= n; i ++ ) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
            return ;
        }

        // 开始进行dfs
        for(int i = 1; i <= n; i ++ ) {
            if(!st[i]) { // 表明 这个数 是 可以去用的
                st[i] = true;
                a[len] = i;
                dfs(len + 1);

                // 注意要回溯
                st[i] = false;
            }
        }
    }
}
